package A一周刷爆LeetCode.A基础班.G图;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

/**
 * @author wei.zhao
 * @description: 拓扑排序算法
 * @date 2022年03月04日 16:33
 */
public class Code03_TopologySort {

    public static List<Node> sortedTopology(Graph graph) {
        LinkedList<Node> list = new LinkedList<>();
        if (graph == null) {
            return list;
        }
        LinkedList<Node> popList = new LinkedList<>();
        // 记录下每个节点的入度
        HashMap<Node, Integer> inMap = new HashMap<>();
        for (Node node : graph.nodes.values()) {
            inMap.put(node, node.in);
            if (node.in == 0) {
                popList.add(node);
            }
        }
        while (!popList.isEmpty()) {
            Node node = popList.pop();
            list.add(node);
            for (Node next : node.nexts) {
                inMap.put(next, inMap.get(next) - 1);
                if (inMap.get(next) == 0) {
                    popList.add(next);
                }
            }
        }
        return list;
    }

}
